package leetcode.weekly.week297;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.H;

//Solution4Test
public class Solution7 implements IDebug {

	// Solution4Test
	public long distinctNames(String[] ideas) {
		Set<String> set = new HashSet<>();
		Map<String, int[]> keyTail = new HashMap<>();
		int[] keyHead = new int[26];
		for (int i = 0; i < ideas.length; i++) {
			String string = ideas[i];
			set.add(string);
			char head = string.charAt(0);
			String tail = string.substring(1);
			int[] heads = keyTail.getOrDefault(tail, new int[] { 0, 0 });
			int headIndex = 1 << (head - 'a');
			if ((heads[0] & headIndex) == 0) {
				heads[0] |= headIndex;
				heads[1] += 1;
				keyTail.put(tail, heads);
			}
			keyHead[head - 'a']++;
		}
		int[] startWith = new int[26];
		Map<String, Integer> endWith = new HashMap<>();
		for (int i = 0; i < startWith.length; i++) {
			char c = (char) (i + 'a');
			int cnt = 0;
			for (Map.Entry<String, int[]> tail : keyTail.entrySet()) {
				String t = tail.getKey();
				int[] info = tail.getValue();
				if (set.contains(c + t)) {
					cnt += info[1];
					int num = endWith.getOrDefault(t, 0);
					endWith.put(t, num + keyHead[c - 'a']);
				}
			}
			startWith[i] = cnt;
		}
		int total = ideas.length;
		long ans = 0;
		for (int i = 0; i < ideas.length; i++) {
			String string = ideas[i];
			char head = string.charAt(0);
			String tail = string.substring(1);
			int sub1 = startWith[head - 'a'];
			int sub2 = endWith.get(tail);
//			int add1 = keyHead[head - 'a'] - 1;
//			int add2 = keyTail.get(tail)[1] - 1;
			ans += (long) (total - sub1 - sub2 + keyTail.get(tail)[1]);// + add1 + add2 + 1
		}
		return ans;
	}

	@Override
	public void debug4() {
		// ["ra","df","dk","rk"]
		// ["pzydbfwiw","ringlxh","dcn","drmvufbt","qzydbfwiw","rrmvufbt"]
//		["pzydbfwiw","ow","ssipb","jucpsquexm","ffuzder","uftruik","ringlxh","csdbtsvg","openygbaix","dcn","sz","ejfpsea","vjfpsea","drmvufbt","qzydbfwiw","lqxik","rrmvufbt"]
		// ["pzydbfwiw","lvvyshmd","ow","ssipb","jucpsquexm","ffuzder","uftruik","ringlxh","sjlxouiv","csdbtsvg","openygbaix","dcn","sze","ttptd","atxp","ejfpsea","vjfpsea","drmvufbt","qzydbfwiw","lqxik","bjo","rrmvufbt"]
//		H.compare(2, this.distinctNames(H.str2array2("[\"ra\",\"df\",\"dk\",\"rk\"]")));
//		H.compare(2, this.distinctNames(H.str2array2("[\"ringlxh\",\"dcn\",\"drmvufbt\",\"rrmvufbt\"]")));
//		H.compare(18, this.distinctNames(H.str2array2("[\"pzydbfwiw\",\"ringlxh\",\"dcn\",\"drmvufbt\",\"qzydbfwiw\",\"rrmvufbt\"]")));
//		H.compare(438, this.distinctNames(H.str2array2("[\"pzydbfwiw\",\"lvvyshmd\",\"ow\",\"ssipb\",\"jucpsquexm\",\"ffuzder\",\"uftruik\",\"ringlxh\",\"sjlxouiv\",\"csdbtsvg\",\"openygbaix\",\"dcn\",\"sze\",\"ttptd\",\"atxp\",\"ejfpsea\",\"vjfpsea\",\"drmvufbt\",\"qzydbfwiw\",\"lqxik\",\"bjo\",\"rrmvufbt\"]")));
//		["pzydbfwiw","lvvyshmd","ow","ssipb","jucpsquexm","ffuzder","uftruik","ringlxh","jz","sjlxouiv","csdbtsvg","openygbaix","dcn","rr","hwql","ok","yy","sze","ttptd","atxp","ejfpsea","vjfpsea","lj","drmvufbt","qzydbfwiw","lqxik","bjo","rrmvufbt"]
//		H.compare(716, this.distinctNames(H.str2array2(
//				"[\"pzydbfwiw\",\"lvvyshmd\",\"ow\",\"ssipb\",\"jucpsquexm\",\"ffuzder\",\"uftruik\",\"ringlxh\",\"jz\",\"sjlxouiv\",\"csdbtsvg\",\"openygbaix\",\"dcn\",\"rr\",\"hwql\",\"ok\",\"yy\",\"sze\",\"ttptd\",\"atxp\",\"ejfpsea\",\"vjfpsea\",\"lj\",\"drmvufbt\",\"qzydbfwiw\",\"lqxik\",\"bjo\",\"rrmvufbt\"]")));
//		H.compare(4934, this.distinctNames(H.str2array2(
//				"[\"sfuzder\",\"spklurny\",\"kvdolme\",\"kbbdklkpgk\",\"za\",\"mdbsmnjiu\",\"pzydbfwiw\",\"lvvyshmd\",\"ow\",\"ssipb\",\"jucpsquexm\",\"ffuzder\",\"uftruik\",\"ringlxh\",\"jz\",\"sjlxouiv\",\"csdbtsvg\",\"openygbaix\",\"dcn\",\"r\",\"hwql\",\"ok\",\"y\",\"sze\",\"ttptd\",\"atxp\",\"ejfpsea\",\"vjfpsea\",\"lj\",\"drmvufbt\",\"zxambug\",\"ozpxq\",\"qzydbfwiw\",\"lqxik\",\"bjo\",\"rrmvufbt\",\"jvl\",\"rzxaaa\",\"nmfydhawa\",\"shlwkf\",\"rcl\",\"hhn\",\"yrmcsc\",\"yieuzizaeh\",\"nrmvufbt\",\"rinsldgdpp\",\"wqg\",\"tyhkgqcu\",\"rsdbtsvg\",\"zvehtqiqxa\",\"jtz\",\"mjaguebiy\",\"fztbpozhf\",\"zzpxq\",\"ue\",\"foktqxiqe\",\"ztf\",\"dn\",\"lxambug\",\"kinsldgdpp\",\"jhn\",\"k\",\"i\",\"qxtava\",\"roktqxiqe\",\"hr\",\"bwzw\",\"mot\",\"cadj\",\"x\",\"bcep\",\"u\",\"kzydbfwiw\",\"ahku\",\"ijo\"]")));
//		H.compare(2, this.distinctNames(H.str2array2("[\"aaa\",\"baa\",\"caa\",\"bbb\",\"cbb\",\"dbb\"]")));
		H.compare(6, this.distinctNames(H.str2array2("[\"coffee\",\"donuts\",\"time\",\"toffee\"]")));
//		H.compare(0, this.distinctNames(H.str2array2("[\"lack\",\"back\"]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution7 so = new Solution7();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
